package com.sx.sx1.lintcode.day717;

public class LC380 {


    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
            next = null;
        }
    }


    static class Solution {
        /**
         * @param headA: the first list
         * @param headB: the second list
         * @return: a ListNode
         */
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            if (headA == null || headB == null) return null;
            ListNode pa = headA;
            ListNode pb = headB;

            while (pa != pb) {
                pa = pa == null ? headB : pa.next;
                pb = pb == null ? headA : pb.next;
            }

            return pa;

            /*
            leetcode 160. 相交链表

题意：给定两个链表A、B的表头节点，找到链表交叉节点（地址值相同）。链表A长度为m，链表B长度为n，范围在[1, 3e4]

题解1：
根据哈希表去重的原理，使用哈希表集合HashSet来维护链表节点，默认比较节点地址值。将链表A中的节点全部add进HashSet中，然后遍历链表B中的节点，如果发现某节点在HashSet存在则找到交叉节点。

时间复杂度：O(n + m)
空间复杂度：O(m)

HashSet实现代码
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
// * }
//
//            public class Solution {
//                public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//                    Set<ListNode> set = new HashSet<>();
//                    while(headA != null) {
//                        set.add(headA);
//                        headA = headA.next;
//                    }
//                    while(headB != null) {
//                        if(set.contains(headB)) {
//                            return headB;
//                        }
//                        headB = headB.next;
//                    }
//                    return null;
//                }
//            }
//            题解2：
//            维护链表A指针pA，链表B指针pB
//            这两个指针分别从链表头开始往后遍历，遍历到表尾后则指向另一个链表头继续遍历，直至找到交叉节点，或者两个指针同时再次遍历到表尾。
//            PS：当两个指针都指向另一个链表时，就表明，两个指针当前所在位置距离表尾的长度是一致的，通过这种方式可以消除两个链表长度不统一。
//
//            时间复杂度：O(m+n)
//            空间复杂度：O(1)
//
//            双指针实现代码
///**
// * Definition for singly-linked list.
// * public class ListNode {
// *     int val;
// *     ListNode next;
// *     ListNode(int x) {
// *         val = x;
// *         next = null;
// *     }
// * }
// */
//            public class Solution {
//                public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//                    ListNode pA = headA, pB = headB;
//                    while(pA != null || pB != null) {
//                        if(pA == pB) return pA;
//                        pA = pA == null ? headB : pA.next;
//                        pB = pB == null ? headA : pB.next;
//                    }
//                    return null;
//                }
//            }
//            分类: 算法 / 力扣算法题
//            好文要顶 关注我 收藏该文 微信分享
//            沙汀鱼
//            粉丝 - 0 关注 - 0
//                    +加关注
//            00
//            升级成为会员
//« 上一篇： 【一个队列实现栈】Java队列——Queue接口-LinkedList实现类
//» 下一篇： 【反转链表】while循环/递归
//            posted @ 2023-12-13 13:27  沙汀鱼  阅读(5)  评论(0)  编辑  收藏  举报
//https://www.cnblogs.com/Eve7Xu/p/17898832.html

        }
    }


    public static void main(String[] args) {
        ListNode t1 = null;
        ListNode tail = t1;
        for (int i = 7; i < 14; i++) {
            if (t1 == null) {
                t1 = new ListNode(i);
                tail = t1;
            } else {
                ListNode node = new ListNode(i);
                tail.next = node;
                tail = node;
            }
        }


        ListNode t2 = null;
        ListNode t3 = null;
        ListNode tail2 = t1;
        for (int i = 1; i < 14; i++) {
            if (t2 == null) {
                t2 = new ListNode(i);
                tail2 = t2;
            } else {
                ListNode node = new ListNode(i);

                tail2.next = node;
                tail2 = node;
                if(i==7){
                    t3 = tail2;
                }
            }
        }

        ListNode cur = t2;
        while (cur!=null){
            cur = cur.next;
            if(cur.next.val ==7){
                t3 = cur.next;
                break;
            }
        }
        System.out.println(new Solution().getIntersectionNode(t1, t3));
    }
}

/*
LintCode-Logo
搜索题目、标签、题集
中文
avatar
您有199条未读消息，请及时查看
380 · 两个链表的交叉
算法
中等
通过率
47%

题目
题解35
笔记
讨论99+
排名
记录
描述
请写一个程序，找到两个单链表最开始的交叉节点。

最短时间刷“透”算法面试：《66页算法宝典》.pdf

微信添加【jiuzhangfeifei】备注【66】领取


如果两个链表没有交叉，返回null。
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
样例
样例 1：

输入：
	A:          a1 → a2
	                   ↘
	                     c1 → c2 → c3
	                   ↗
	B:     b1 → b2 → b3
输出：c1
解释：在节点 c1 开始交叉。
样例 2:

输入:
Intersected at 6
1->2->3->4->5->6->7->8->9->10->11->12->13->null
6->7->8->9->10->11->12->13->null
输出: Intersected at 6
解释：begin to intersect at node 6.
挑战
需满足 O(n) 时间复杂度，且仅用 O(1) 内存。

标签
企业
Bloomberg
Airbnb
Amazon
Microsoft
相关题目

102
带环链表
中等

103
带环链表 II
困难
推荐课程

Twitter 后端系统 - Python 项目实战
从0项目经验到深度后端项目操盘，FB架构师万行代码还原真实开发环境，14周简历镀金
360/1856
已开启智能提示
发起考试
30 分 00 秒
12345678910111213141516171819202122
 */
